package com.njupt.Tree;

import java.util.Deque;
import java.util.LinkedList;

/**
 * @Author: wujiaming
 * @CreateTime: 2025/2/20 19:25
 * @Description: 543. 二叉树的直径
 * @Version: 1.0
 */


public class DiameterOfBinaryTree_543 {
    
    public int ans = 1;

    public int diameterOfBinaryTree(TreeNode root) {
       depth(root);
       return this.ans-1;

    }



    /**
     * 1、定义一个树的最大节点数ans =左子树的深度L与右子树的深度R +1 = L+ R +1
     * 2、树的直径 = ans -1
     * 3、转化为：对于一个节点求左子树的深度L 和 右子树的深度 R
     * @param root
     * @return
     */
    private int depth(TreeNode root) {

        if(root == null){
            return 0;
        }
        int left = depth(root.left);        //计算当前节点左子树的深度
        int right = depth(root.right);      //计算当前节点右子树的深度
        this.ans = Math.max(this.ans,left + right +1);
        return Math.max(left,right) +1;     //返回当前节点的深度
    }



    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
//        root.right = new TreeNode(3);
//        root.left.left = new TreeNode(4);
//        root.left.right = new TreeNode(5);

        DiameterOfBinaryTree_543 test = new DiameterOfBinaryTree_543();
        System.out.println(test.diameterOfBinaryTree(root));
    }
}
